The present invention relates to language modeling and parsing algorithms. More particularly, the present invention relates to eliminating left recursion from grammars or other similar models.
Accurate speech recognition by computer requires more than just an acoustic model to select the correct word spoken by the user. In other words, if a speech recognizer must choose or determine which word has been spoken, if all words have the same likelihood of being spoken, the speech recognizer will typically perform unsatisfactorily. A language model provides a method or means of specifying which sequences of words in the vocabulary are possible, or at least most likely.
Computer speech recognition is usually implemented using top-down language processing. Top-down language processing begins with the largest unit of language to be recognized, such as a sentence, and processes it by analyzing it into smaller units, such as phrases, which in turn, are analyzed into yet smaller units, such as words.
One common technique of classifying is to use a formal grammar. The formal grammar defines the sequence of words that the application will allow. One particular type of grammar is known as a xe2x80x9ccontext-free grammarxe2x80x9d (CFG), which allows complex linguistic patterns to be specified. However, topdown language processing systems that use a context free grammar do not permit xe2x80x9cleft recursionxe2x80x9d within the grammar. xe2x80x9cLeft recursionxe2x80x9d is present in a CFG when a definition of a category can begin with a smaller phrase of the same category. In the English language, xe2x80x9cleft recursionxe2x80x9d can be illustrated by the following CFG:
Sxe2x86x92NP VP [A sentence (S) can consist of a noun phrase (NP) followed by a verb phrase (VP).]
NPxe2x86x92Det N [A noun phrase can consist of a determiner (Det) followed by a noun (N).]
Detxe2x86x92NP""s [A determiner can consist of a noun phrase followed by xe2x80x9c""sxe2x80x9d]
FIG. 1 is a pictorial representation of the rules or rule expressions above. xe2x80x9cLeft recursionxe2x80x9d is present in this partial grammar because the definition of a noun phrase (NP) includes a determiner (DET), the definition of which includes a noun phrase in the left-most position on the right-hand side of the rule expression. Augmented with appropriate additional rule expressions and dictionary entries, this grammar will define such sentences as:
xe2x80x9cJohn sleeps.xe2x80x9d
xe2x80x9cJohn""s mother sleeps.xe2x80x9d
xe2x80x9cJohn""s mother""s dog sleeps.xe2x80x9d
xe2x80x9cLeft recursionxe2x80x9d cannot be directly coded in the grammar and used by a top-down language processing engine. However, it has been known how to transform a CFG having left recursion into Greibach normal form. (Transforming a grammar results in a different grammar that permits the same sequence of words.) Greibach normal form is non-left-recursive. Unfortunately, converting a CFG to Greibach normal form can realize a grammar that is far too large to be used, or sometimes, even completely generated. In other words, the resulting CFG contains or would contain too many rules to define the desired sentences. This situation creates two problems. First, storage capabilities may not exist for storing the complete set of rules of the transformed grammar. Second, processing or traversal of the grammar during speech recognition (or other language processing such as parsing) may take too long.
There thus is a need to improve context-free grammars used by top-down language processing systems such as speech recognizers or parsers. For instance, there is a need to transform a left-recursive context-free grammar into a non-left-recursive grammar without the latter becoming too large.
A method for transforming a first set of rule expressions forming a first grammar to a second set of rule expressions forming a second grammar includes identifying at least one left-recursive category of the first grammar; and applying a left-corner transform to substantially only the left-recursive rule expressions of the first grammar in forming the second grammar. The method can be executed on a suitable computer wherein instructions are provided on a computer readable medium.
A second broad aspect of the present invention is a method for building a language model by transforming a first set of rule expressions forming a first grammar to a second set of rule expressions forming a second grammar, the method including:
replacing a set of rule expressions of the form,
Axe2x86x92X1xcex21, . . . , Axe2x86x92Xnxcex2n
xe2x80x83with
Axe2x86x92A-non-left-rec A-non-left-recxe2x86x92X1xcex21. . . A-non-left-recxe2x86x92Xnxcex2n
where A is a left-recursive category, X1 . . . Xn are each any word or non-left-recursive category of the first grammar, xcex21 . . . xcex2n are each a sequence (possibly a null sequence) of words and/or categories of the first grammar, and A-non-left-rec is a newly defined category. The method can be executed on a suitable computer wherein instructions are provided on a computer readable medium.